1. Field of the Invention
The present invention relates generally to a route search method, and, more particularly, to a method of raising the probability of searching a plurality of routes not by way of the same node, and to a network system to which the method is applied.
2. Description of the Related Art
In the case where a data communication is carried on in a network containing a plurality of nodes, for example, in a broadcasting network which transmits a picture signal (containing a voice), a plurality of broadcasting stations are connected to a transmission line as each node, and are configured so as to transmit the picture signal from a certain key station to another key station by way of the plurality of nodes.
Herein, in order to increase the reliability in a broadcast, the same picture signal is normally transmitted as a picture signal transmission from a certain one station to a reception station through a plurality of routes. Thus, the reception station switches faults in the routes to be transmitted through the one route into the picture signal to be transmitted through another route for reception, whereby it is possible to receive the picture signal without generating a disorder of the picture.
In order to ensure such an aspect, it is necessary that the plurality of routes have previously been set in a network under prescribed conditions prior to a start of the operation and also after the start of the operation. For this reason, a technique for searching a route to be set from the plurality of routes in the network comes to be required.
As a conventional technique for acquiring a route at the shortest distance out of all the routes linking from a certain initial node to a terminal node in the network, the Dijkstra method is well known. This method is, for example, an algorithm which introduces the most advantageous one route in an element by a matrix calculation with an element (distance, cost, or the like) in all the routes linking between the nodes as a matrix.
FIG. 1 is a diagram for explaining a concept of such the Dijkstra method, and as a step of searching the plurality of routes, a first shortest route is searched (a first shortest route search a) and succeedingly n pieces of remaining routes are searched (an n route search b).
That is, the Dijkstra method, in FIG. 1, registers a section between adjoining two nodes as an element, and a distance in section unit as an attribute. And, this algorithm calculates the distance between the sections linking all the adjacent nodes from a certain initial node, and then further calculates the distance linking all the adjacent nodes from respective adjacent nodes, and determines the shortest route in the distance of the sections linked up to the terminal node by repeating the above.
In the case where such the algorithm is applied, it is possible to present the one shortest route. However, in the case where the plurality of routes are necessary, there is a possibility that the nodes or sections are overlapped each other. FIG. 2 shows one example of the network, and in the case where a part of the nodes or sections is unusable, there is a possibility that the plurality of routes are unusable.
That is, in FIG. 2, a network configured by a node A to a node I is assumed. The initial node is designated as the node A and the terminal node is designated as the node I, and in the case where the first route to be searched by the Dijkstra method is A B E H I, a second route is bound to pass by way of the same node with the first route. Accordingly, in the case where the common node is unusable, either route is unusable.
Furthermore, when the first route is not treated as an object (is set so as not to pass the same node or same section) and the second route and forward are acquired, as the other than the shortest route has to be used, the second route and forward are a devious route, or are not found, and then there is a possibility that the use in the plurality of shortest routes is impossible. In this manner, in the case of the Dijkstra method, a difference in conditions between the first route and the second route is increased.